package com.linchong.binarysearch.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-28 20:40
 * @Description: SearchInBigSortedArray$
 *  给定一个大的有序数组，和target,查找target在其中的位置，找不到返回-1
 *
 *  山脉数组中查找目标值
 *  给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
 *
 * 如果不存在这样的下标 index，就请返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-in-mountain-array
 *
 */
public class SearchInBigSortedArray {

	/**
	 * nums为题目给定函数
	 */
   private int[] nums;
	/**
	 * 第一个数，第二个数，第四个数，第八个数...比较k
	 * log2k次，到达k~2k附近
	 * @return
	 */
	public int searchBigSortedArray(int target){
		int index = 1;

		// logk时间找到k
		while (nums[index-1]<target){
			index = index*2;
		}
		int start = index/2;
		int end = index-1;
		while (start+1<end){
			int mid = start+(end-start)/2;
			if(nums[start]<target){
				start = mid;
			}else{
				end = mid;
			}
		}

		if(nums[start]<=target){
			return start;
		}

		if(nums[end]<=target){
			return end;
		}
		return -1;
	}
}
